package com.wenhao.leetcode.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 题目：https://leetcode-cn.com/problems/combination-sum/
 *
 * 思路：
 * 递归的方法
 * 如果我要找得target为7
 * 当前的数字为2
 * 那么我只需要求所有和为5的可能，然后再这些组合的基础上添加一个数字2
 * 如果当前的数字为8
 * 那么我们需找和为-1的可能，实际是不可能，那么可以返回一个空的集合，同时也说明当前的数字是不可能出现在当前要求的组合里面的，可以尝试当前的下一个数字
 *
 * 为什么我的递归回溯代码写得丑陋？
 * 还是因为思路不够清晰
 *
 * @author Wenhao Tong
 * @create 2021-06-27 21:50
 */
public class LeetCode39 {
    public static void main(String[] args) {
        LeetCode39 leetCode39 = new LeetCode39();
        List<List<Integer>> lists = leetCode39.combinationSum(new int[]{2, 3, 6, 7}, 7);
        for (List<Integer> list : lists) {
            for (Integer num : list) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }


    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<Integer> path = new ArrayList<>();
        dfs(0,candidates,target,path);
        return result;
    }

    /**
     * 结果集储存在一个类的属性中
     */
    List<List<Integer>> result = new ArrayList<>();

    /**
     *
     * @param index 搜索起点
     * @param candidates 候选数组
     * @param target 我们在不断地缩小target的规模
     * @param path 从根节点到叶子节点的路径，数据结构为一个栈
     */
    public void dfs (int index,int[] candidates,int target,List<Integer> path) {

//        if (index == candidates.length) return new ArrayList<>();
//        if (candidates[index] == target) {
//            List<Integer> list = new ArrayList<>();
//            list.add(target);
//            List<List<Integer>> res = new ArrayList<>();
//            res.add(list);
//            return res;
//        }
        if (target < 0) return;
        // 这里在第一次写的时候犯了一个错误：直接把path填入result中，这样最后的结果是两个空的path
        if (target == 0) {
            List<Integer> res = new ArrayList<>(path);
            result.add(res);
            return;
        }
//        int nextTarget = target - candidates[index];
//        List<List<Integer>> dfs;
//        if (nextTarget >= 0) {
//            path.add(candidates[index]);
//            dfs(index, candidates, nextTarget,path);
//        } else {
//            dfs(index + 1, candidates, target,path);
//        }
//        return result;
        for (int i = index; i < candidates.length; i++) {
            if (target - candidates[i] < 0) {
                break;
            }
            path.add(candidates[i]);

            // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
            dfs(i,candidates,target - candidates[i],path);

            // 状态重置
            path.remove(path.size() - 1);
        }
    }



}
